package com.company.Link;

import java.security.KeyStore;

/**
 * @author 关敬元
 * @Description
 * @date 2019/11/29
 */
public class MyMap {
    private MyLink[] table;

    private int DEFAULT_TABLE_CAPACITY = 16;//建自己的列表
    private int POW = 4;  //数组下标
    private int size;//列表长度
    private double FILLDIVISOR = 0.75;

    public MyMap() {
        this.table = new MyLink[DEFAULT_TABLE_CAPACITY];
    }

    /**
     * 存放数据到table中
     *
     * @param key
     * @param value
     */
    public void put(Object key, Object value) {
        //先计算下标
        //计算链表容量和填充因子  如果不够大就应该扩容
        MyLink link = getLinkByKey(key);

        //检查容量 有可能扩容
        calcCapacity(calcFlag(key));
        //link重新获取心的链表（防止扩容 链表地址变更）
        link = getLinkByKey(key);


        //查找链表中是否有相同的KEY 就覆盖
        MyLink.Entry mod = null;
        for (int i = 0; i < link.getSize(); i++) {
            if (link.indexOf(i).getKey() == key) {
                mod = link.indexOf(i);
                mod.setValue(value);
                break;
            }
        }
        //如果没有相同就添加数据到链表上
        if (mod == null) {
            link.add(key, value);
        }
        //有可能你出现的链表是一个自己new 新链表
        table[calcFlag(key)] = link;
    }

    /**
     * 按照key获取链表
     *
     * @param key
     * @return
     */
    public MyLink getLinkByKey(Object key) {
        //获得桶数组的下标
        int flag = calcFlag(key);//按键搜下标
        MyLink link = null;
        //到对应的数组位置查看数组是否为null;
        if (table[flag] == null) {
            //创建链表并将数据存放到链表中  并把链表存放到table中
            link = new MyLink();
        } else {
            link = table[flag];
        }
        return link;
    }

    /**
     * 按照桶表的下标 获取链表并计算容量 决定是否扩容
     *
     * @param flag //桶表上的下标
     */
    private void calcCapacity(int flag) {
        //容量不够就扩容
        //获取链表
        MyLink link = table[flag]==null?new MyLink():table[flag];
        //根据链表元素个数和数组长度计算是否扩容
        if (DEFAULT_TABLE_CAPACITY * FILLDIVISOR <= link.getSize() + 1) {
            resize();
        }
    }

    private void resize() {
        //新的桶数组建立
        //重新设置初始化参数
        POW++;
        DEFAULT_TABLE_CAPACITY = DEFAULT_TABLE_CAPACITY << 1;  //DEFAULT_TABLE_CAPACITY*2也可以但是计算比较慢
        size = 0;
        //将原桶表保存到oldTab中
        MyLink[] oldTab = this.table;
        //在table中开辟一个新尺寸的桶表
        table = new MyLink[DEFAULT_TABLE_CAPACITY];
        //将原map中的数组都提出来，并重新存放到新的链表tab中
        //桶表循环
        for (int i = 0; i < oldTab.length; i++) {
            if (oldTab[i] == null) {
                continue;
            }
            //链表循环
            for (int j = 0; j < oldTab[i].getSize(); j++) {
                final MyLink.Entry entry = oldTab[i].indexOf(j);
                //将数据取出存放到新的数组中
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    /**
     * 计算下标的核心公式
     * @param key
     * @return
     */
    private int calcFlag(Object key){
        if (key==null){
            return 0;
        }else{
            return key.hashCode()&((1<<POW)-1);
        }
    }

    /**
     * 按key删除对应数据
     *
     * @param key
     */
    //先找环
    public void remove(Object key) {
        //获取桶表下标，将key转成hash值
        final int flag = calcFlag(key);
        //在桶表上找到对应的元素
        MyLink link = table[flag];
        //检查桶表上是否存在
        if (link != null) {
            //循环搜索用户的键
            for (int i = 0; i < link.getSize(); i++) {
                MyLink.Entry tmp = link.indexOf(i);
                if (tmp.getKey() == key) {
                    link.remove(i);
                    size--;
                    break;
                }
            }
        }
    }

    /**
     * 在map中按key获取value
     *
     * @param key
     * @return
     */
    public Object get(Object key) {
        MyLink ml = getLinkByKey(key);
        if (ml == null) {
            return ml;
        } else {
            return ml.get(key);
        }
    }

    /**
     * 获取map中有多少个元素
     * @return
     */
    public int getSize(){
        return size;
    }
}

